# url= https://leetcode.cn/problems/longest-univalue-path/

class Solution(object):
    max_val = 0
    def dfs(self, root):
        left = self.dfs(root.left) if root.left != None else 0
        right = self.dfs(root.right) if root.right != None else 0

        res = 0
        if root.left != None and root.val == root.left.val:
            res = left + 1
        
        if root.right != None and root.val == root.right.val:
            res += right + 1
        
        self.max_val = max(self.max_val, res)
        return res

    
    def longestUnivaluePath(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0
        self.dfs(root)
        return self.max_val